/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2019年12月19日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.practice;

/**
 * @Type A20191218_1219_1225_BST
 * @Desc
 * @author 52489
 * @date 2019年12月19日
 * @Version V1.0
 */
public class A20191218_1219_1225_BST {

    public static void main(String[] args) {
        A20191218_1219_1225_BST BST = new A20191218_1219_1225_BST();
        Node node = new A20191218_1219_1225_BST().new Node(39);
        BST.root = node;
        BST.insert(24);
        BST.insert(64);
        BST.insert(23);
        BST.insert(30);
        BST.insert(53);
        BST.insert(60);
        BST.insert(27);
        BST.insert(28);
        BST.midShow(BST.root);
        System.out.println("------------");
        Node node2 = BST.search(30);
        // BST.delete(39);
        // BST.delete2(24);
        BST.delete(24);
        System.out.println("------------");
        BST.midShow(BST.root);
    }

    public Node root;

    class Node {
        int data;
        Node left;
        Node right;

        /**
         * @param data
         */
        public Node(int data) {
            super();
            this.data = data;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getright() {
            return right;
        }

        public void setright(Node right) {
            this.right = right;
        }

    }

    public void insert(int data) {

        if (null == root) {
            throw new RuntimeException("初始化root");
        }
        Node tmp = root;
        while (true) {
            if (data > tmp.data) {
                if (null != tmp.right) {
                    tmp = tmp.right;
                } else {
                    Node node = new Node(data);
                    tmp.right = node;
                    return;
                }
            } else {
                if (null != tmp.left) {
                    tmp = tmp.left;
                } else {
                    Node node = new Node(data);
                    tmp.left = node;
                    return;
                }
            }
        }
    }

    Node search(int key) {
        Node tmp = root;
        while (key < tmp.data) {
            if (null == tmp.left) {
                return null;
            }
            tmp = tmp.left;
        }

        while (key > tmp.data) {
            if (null == tmp.right) {
                return null;
            }
            tmp = tmp.right;
        }

        return tmp;

    }

    void delete(int data) {
        Node tmp = root;
        Node nodeParent = null;
        Node node = null;
        if (data == tmp.data) {
            if (null != tmp.right && null != tmp.left) {
                tmp = tmp.right;
                while (null != tmp.left) {
                    tmp = tmp.left;
                }
                tmp.left = root.left;
                root = root.right;
            }
        } else {
            // 遍历找到了节点和他的父节点
            while (data < tmp.data) {
                if (null == tmp.left) {
                    return;
                }
                if (tmp.left.data == data) {
                    nodeParent = tmp;
                    node = tmp.left;
                    break;
                }
                tmp = tmp.left;
            }

            while (data > tmp.data) {
                if (null == tmp.right) {
                    return;
                }
                if (tmp.right.data == data) {
                    nodeParent = tmp;
                    node = tmp.right;
                    break;
                }
                tmp = tmp.right;
            }

            if (null != node) {
                // 左右孩子都为空直接删掉
                if (null == node.left && null == node.right) {
                    nodeParent.left = null;
                } else {
                    if (null == node.left) {
                        nodeParent.left = node.right;
                        return;
                    }
                    if (null == node.right) {
                        nodeParent.left = node.right;
                        return;
                    }
                    // 右子树替换节点
                    Node tmpLeftChild = node.right;
                    // 找到右子树的最后左子节点替换为
                    while (null != tmpLeftChild.left) {
                        tmpLeftChild = tmpLeftChild.left;
                    }
                    tmpLeftChild.left = node.left;
                    nodeParent.left = node.right;
                }
            }
        }

    }

    void delete2(int data) {
        Node tmp = root;
        Node nodeParent = null;
        Node node = null;
        if (data == tmp.data) {
            if (null != tmp.right && null != tmp.left) {
                tmp = tmp.right;
                while (null != tmp.left) {
                    tmp = tmp.left;
                }
                tmp.left = root.left;
                root = root.right;
            }
        } else {
            // 遍历找到了节点和他的父节点
            while (data < tmp.data) {
                if (null == tmp.left) {
                    return;
                }
                if (tmp.left.data == data) {
                    nodeParent = tmp;
                    node = tmp.left;
                    break;
                }
                tmp = tmp.left;
            }

            while (data > tmp.data) {
                if (null == tmp.right) {
                    return;
                }
                if (tmp.right.data == data) {
                    nodeParent = tmp;
                    node = tmp.right;
                    break;
                }
                tmp = tmp.right;
            }

            if (null != node) {
                if (null == node.left && null == node.right) {
                    nodeParent.left = null;
                } else {
                    if (null == node.right) {
                        nodeParent.left = node.left;
                        return;
                    }
                    // 删除的是左子节点
                    if (node == nodeParent.left) {
                        Node mixLeftChildParent = node.right;
                        while (null != mixLeftChildParent.left && null != mixLeftChildParent.left.left) {
                            mixLeftChildParent = mixLeftChildParent.left;
                        }
                        Node mixLeftChild = mixLeftChildParent.left;
                        Node replaceNode = new Node(mixLeftChild.data);
                        // mixLeftChildParent的左子树替换为mixLeftChild的右子树不管有没有
                        mixLeftChildParent.left = mixLeftChild.right;
                        // 替换的节点左子树和右子树设置
                        replaceNode.left = node.left;
                        replaceNode.right = node.right;
                        // 父节点的左子树指向替代的节点
                        nodeParent.left = replaceNode;
                    }
                }
            }

        }
    }

    public void midShow(Node node) {
        if (null != node) {
            midShow(node.left);
            System.out.println(node.data);
            midShow(node.right);
        }
    }

}
